home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_guile.idb / usr / freeware / share / guile / 1.4 / ice-9 / q.scm.z / q.scm
Text File  |  2002-07-08  |  4KB  |  149 lines
  1. ;;;; q.scm --- Queues
  2. ;;;;
  3. ;;;;     Copyright (C) 1995 Free Software Foundation, Inc.
  4. ;;;; 
  5. ;;;; This program is free software; you can redistribute it and/or modify
  6. ;;;; it under the terms of the GNU General Public License as published by
  7. ;;;; the Free Software Foundation; either version 2, or (at your option)
  8. ;;;; any later version.
  9. ;;;; 
  10. ;;;; This program is distributed in the hope that it will be useful,
  11. ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. ;;;; GNU General Public License for more details.
  14. ;;;; 
  15. ;;;; You should have received a copy of the GNU General Public License
  16. ;;;; along with this software; see the file COPYING.  If not, write to
  17. ;;;; the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
  18. ;;;; Boston, MA 02111-1307 USA
  19. ;;;; 
  20.  
  21. (define-module (ice-9 q))
  22.  
  23. ;;;;
  24. ;;; Q: Based on the interface to 
  25. ;;;
  26. ;;; "queue.scm"  Queues/Stacks for Scheme 
  27. ;;;  Written by Andrew Wilcox (awilcox@astro.psu.edu) on April 1, 1992.
  28. ;;;
  29.  
  30. ;;;;
  31. ;;; {Q}
  32. ;;;
  33. ;;; A list is just a bunch of cons pairs that follows some constrains,
  34. ;;; right?  Association lists are the same.  Hash tables are just
  35. ;;; vectors and association lists.  You can print them, read them,
  36. ;;; write them as constants, pun them off as other data structures
  37. ;;; etc. This is good.  This is lisp.  These structures are fast and
  38. ;;; compact and easy to manipulate arbitrarily because of their
  39. ;;; simple, regular structure and non-disjointedness (associations
  40. ;;; being lists and so forth).
  41. ;;;
  42. ;;; So I figured, queues should be the same -- just a "subtype" of cons-pair 
  43. ;;; structures in general.
  44. ;;;
  45. ;;; A queue is a cons pair:
  46. ;;;        ( <the-q> . <last-pair> )
  47. ;;;
  48. ;;; <the-q> is a list of things in the q.  New elements go at the end
  49. ;;; of that list.
  50. ;;;
  51. ;;; <last-pair> is #f if the q is empty, and otherwise is the last
  52. ;;;pair of <the-q>.
  53. ;;;
  54. ;;; q's print nicely, but alas, they do not read well because the
  55. ;;; eq?-ness of <last-pair> and (last-pair <the-q>) is lost by read.
  56. ;;;
  57. ;;; All the functions that aren't explicitly defined to return
  58. ;;; something else (a queue element; a boolean value) return the queue
  59. ;;; object itself.
  60. ;;;
  61. ;;; The procedure
  62. ;;; 
  63. ;;;        (sync-q! q)
  64. ;;;
  65. ;;; recomputes and resets the <last-pair> component of a queue.
  66. ;;;
  67. (define-public (sync-q! q)
  68.   (set-cdr! q (if (pair? (car q)) (last-pair (car q))
  69.           #f))
  70.   q)
  71.  
  72. ;;; make-q
  73. ;;;  return a new q.
  74. ;;;
  75. (define-public (make-q) (cons '() #f))
  76.  
  77. ;;; q? obj
  78. ;;;   Return true if obj is a Q.
  79. ;;;   An object is a queue if it is equal? to '(() . #f)
  80. ;;;   or it is a pair P with (list? (car P))
  81. ;;;                      and (eq? (cdr P) (last-pair (car P))).
  82. ;;;
  83. (define-public (q? obj)
  84.   (and (pair? obj)
  85.        (if (pair? (car obj))
  86.        (eq? (cdr obj) (last-pair (car obj)))
  87.        (and (null? (car obj))
  88.         (not (cdr obj))))))
  89.  
  90. ;;; q-empty? obj
  91. ;;;  
  92. (define-public (q-empty? obj) (null? (car obj)))
  93.  
  94. ;;; q-empty-check q
  95. ;;;  Throw a q-empty exception if Q is empty.
  96. (define-public (q-empty-check q) (if (q-empty? q) (throw 'q-empty q)))
  97.  
  98. ;;; q-front q
  99. ;;;  Return the first element of Q.
  100. (define-public (q-front q) (q-empty-check q) (caar q))
  101.  
  102. ;;; q-rear q
  103. ;;;  Return the last element of Q.
  104. (define-public (q-rear q) (q-empty-check q) (cadr q))
  105.  
  106. ;;; q-remove! q obj
  107. ;;;  Remove all occurences of obj from Q.
  108. (define-public (q-remove! q obj)
  109.   (set-car! q (delq! obj (car q)))
  110.   (sync-q! q))
  111.  
  112. ;;; q-push! q obj
  113. ;;;  Add obj to the front of Q
  114. (define-public (q-push! q obj)
  115.   (let ((h (cons obj (car q))))
  116.     (set-car! q h)
  117.     (or (cdr q) (set-cdr! q h)))
  118.   q)
  119.  
  120. ;;; enq! q obj
  121. ;;;  Add obj to the rear of Q
  122. (define-public (enq! q obj)
  123.   (let ((h (cons obj '())))
  124.     (if (null? (car q))
  125.     (set-car! q h)
  126.     (set-cdr! (cdr q) h))
  127.     (set-cdr! q h))
  128.   q)
  129.  
  130. ;;; q-pop! q
  131. ;;;  Take the front of Q and return it.
  132. (define-public (q-pop! q)
  133.   (q-empty-check q)
  134.   (let ((it (caar q))
  135.     (next (cdar q)))
  136.     (if (not next)
  137.     (set-cdr! q #f))
  138.     (set-car! q next)
  139.     it))
  140.  
  141. ;;; deq! q
  142. ;;;  Take the front of Q and return it.
  143. (define-public deq! q-pop!)
  144.  
  145. ;;; q-length q
  146. ;;;  Return the number of enqueued elements.
  147. ;;;
  148. (define-public (q-length q) (length (car q)))
  149.